package binarysearchtree

import (
	"fmt"
	"sync"
)

type Item string

// Node 先定义一个节点
type Node struct {
	key   int
	value Item
	left  *Node
	right *Node
}

type ItemBinarySearchTree struct {
	root *Node
	lock sync.RWMutex
}

// Insert 插入一个节点
func (bst *ItemBinarySearchTree) Insert(key int, value Item) {
	bst.lock.Lock()
	defer bst.lock.Unlock()

	n := &Node{key: key, value: value}

	if bst.root == nil {
		bst.root = n
	} else {
		insertNode(bst.root, n)
	}
}

// insertNode 插入节点 在插入时，需要判断插入节点和当前节点的大小关系，保证搜索树的有序性。
func insertNode(node *Node, newNode *Node) {
	if newNode.key < node.key {
		if node.left == nil {
			node.left = newNode
		} else {
			insertNode(node.left, newNode)
		}
	} else {
		if node.right == nil {
			node.right = newNode
		} else {
			insertNode(node.right, newNode)
		}
	}
}

// InOrderTraverse 	中序遍历
func (bst *ItemBinarySearchTree) InOrderTraverse(f func(item Item)) {
	bst.lock.Lock()
	defer bst.lock.Unlock()
	inOrderTraverse(bst.root, f)
}

func inOrderTraverse(node *Node, f func(item Item)) {
	if node != nil {
		inOrderTraverse(node.left, f)
		f(node.value)
		inOrderTraverse(node.right, f)
	}
}

// PreOrderTraverse 前序遍历
func (bst *ItemBinarySearchTree) PreOrderTraverse(f func(item Item)) {
	bst.lock.Lock()
	defer bst.lock.Unlock()
	preOrderTraverse(bst.root, f)
}

func preOrderTraverse(node *Node, f func(item Item)) {
	if node != nil {
		f(node.value)
		preOrderTraverse(node.left, f)
		preOrderTraverse(node.right, f)
	}
}

// PostOrderTraverse 后序遍历
func (bst *ItemBinarySearchTree) PostOrderTraverse(f func(item Item)) {
	bst.lock.Lock()
	defer bst.lock.Unlock()
	postOrderTraverse(bst.root, f)
}

func postOrderTraverse(node *Node, f func(item Item)) {
	if node != nil {
		postOrderTraverse(node.left, f)
		postOrderTraverse(node.right, f)
		f(node.value)
	}
}

// Min 获取最小值 由于树的有序性，想要得到最小值，一直向左查找就可以了。
func (bst *ItemBinarySearchTree) Min() *Item {
	bst.lock.Lock()
	defer bst.lock.Unlock()

	n := bst.root
	if n == nil {
		return nil
	}
	for {
		if n.left == nil {
			return &n.value
		}
		n = n.left
	}
}

// Max 获取最大值 找最右边的就是了
func (bst *ItemBinarySearchTree) Max() *Item {
	bst.lock.Lock()
	defer bst.lock.Unlock()
	n := bst.root
	if n == nil {
		return nil
	}

	for {
		if n.right == nil {
			return &n.value
		}
		n = n.right
	}
}

func (bst *ItemBinarySearchTree) Search(key int) bool {
	bst.lock.Lock()
	defer bst.lock.Unlock()
	return search(bst.root, key)
}

func search(node *Node, key int) bool {
	if node == nil {
		return false
	}
	if key < node.key {
		return search(node.left, key)
	}
	if key > node.key {
		return search(node.right, key)
	}
	return true
}

// 删除操作会复杂一些，分三种情况来考虑：
//如果要删除的节点没有子节点，只需要直接将父节点中，指向要删除的节点指针置为 nil 即可
//如果删除的节点只有一个子节点，只需要更新父节点中，指向要删除节点的指针，让它指向删除节点的子节点即可
//如果删除的节点有两个子节点，我们需要找到这个节点右子树中的最小节点，把它替换到要删除的节点上。然后再删除这个最小节点，因为最小节点肯定没有左子节点，所以可以应用第二种情况删除这个最小节点即可
func (bst *ItemBinarySearchTree) Remove(key int) *Node {
	bst.lock.Lock()
	defer bst.lock.Unlock()
	return remove(bst.root, key)
}

func remove(node *Node, key int) *Node {
	if node == nil {
		return nil
	}
	if key < node.key {
		node.left = remove(node.left, key)
		return node
	}
	if key > node.key {
		node.right = remove(node.right, key)
		return node
	}
	// key == node.key 找到节点了


	//这个节点没有子节点 直接将该节点置为 nil 返回一个 nil 该节点的父节点原本指向该节点的指针也被置为了 nil
	if node.left == nil && node.right == nil {
		node = nil
		return nil
	}

	//该节点的左子节点为 nil 那将该节点变成它的右子节点并返回，该节点的父节点原本指向该节点的指针也变为指向该节点的右子节点，该节点实际上就被删除了
	if node.left == nil {
		node = node.right
		return node
	}
	//同理 该节点的右子节点为 nil 那将该节点变成它的左子节点并返回，该节点的父节点原本指向该节点的指针也变为指向该节点的左子节点，该节点实际上就被删除了
	if node.right == nil {
		node = node.left
		return node
	}

	// 左右都不为空的情况：
	// 1. 找到右子树中最小的节点 因为有序 一定是没有最左的叶子节点
	leftmostrightside := node.right
	for {
		if leftmostrightside != nil && leftmostrightside.left != nil {
			leftmostrightside = leftmostrightside.left
		}else {
			break
		}
	}

	//将当前节点替换为上面找到的右子树中的最小(最左)节点，并且删除那个节点
	node.key ,node.value = leftmostrightside.key, leftmostrightside.value
	node.right = remove(node.right,node.key)
	return node
}

func (bst *ItemBinarySearchTree) String() {
	bst.lock.Lock()
	defer bst.lock.Unlock()
	fmt.Println("------------------------------------------------")
	stringify(bst.root, 0)
	fmt.Println("------------------------------------------------")
}

// internal recursive function to print a tree
func stringify(n *Node, level int) {
	if n != nil {
		format := ""
		for i := 0; i < level; i++ {
			format += "       "
		}
		format += "---[ "
		level++
		stringify(n.left, level)
		fmt.Printf(format+"%d\n", n.key)
		stringify(n.right, level)
	}
}


